18. 四数之和

Similar Question

leading to the advanced question

Solution Tips

方案一: 暴力法 + 剪枝

var fourSum = function(nums, target) {
    // 两个 for 循环遍历, j = i + 1, 形成一个二维矩阵, 三角形的矩阵, 矩阵直接记录形成哈希表
    // 二维矩阵内, 的每个元素, 进行搜索, 但是不能是同行或者同列的, 寻找自身的相反数
    // 而且找出的结果中, 四个元素不能相同, 相同的需要去除才行
    const map = {};
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            let sum = nums[i] + nums[j];
            if (map[sum]) {
                map[sum].push([i, j]);
            }
            else {
                map[sum] = [[i, j]];
            }
        }
    }

    const dirty = [];
    // 找到相反数, 组合后去重, 长度依然为4的才合格
    for (const [key, val] of Object.entries(map)) {
        const positive = map[target-key];
        for (let i = 0; i < val.length; i++) {
            const pairOne = val[i];
            for (let j = 0; j < positive.length; j++) {
                const pairTwo = positive[j];
                const compose = [...new Set([...pairOne, ...pairTwo])]
                if (compose.length === 4) {
                    dirty.push(compose);
                }
            }
        }
    }
    // 对 res 去重, 因为索引一定是有区别的, 所以直接根据和去重即可
    const res = {};
    for (let i = 0; i < dirty.length; i++) {
        const sum = dirty[i].reduce((acc, a) => acc + a, 0);
        if (!res[sum]) {
            res[sum] = dirty[i];
        }
    }
    return Object.values(res).map((indexArr) => indexArr.map(index => nums[index]));
};

// let nums = [1,0,-1,0,-2,2], target = 0
let nums = [2,2,2,2,2], target = 8
console.log(fourSum(nums, target));

这种方法没有办法去重, 去重增加的复杂度太多了

方法二: 排序 + 跳过重复 + 对撞指针

就是三数之和的思路

var fourSum = function(nums, target) {
    // 想办法改成三数之和? 通过等式变化一下位置而已, 还是改变不了本质
    // 参考从两数之和到三数之和, 朴素的增加一层循环吧
    const res = [];
    const n = nums.length;
    nums.sort((a, b) => a - b);

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            let left = j + 1;
            let right = n - 1;

            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];

                if (sum === target) {
                    res.push([nums[i], nums[j], nums[left], nums[right]]);
                }

                if (sum <= target) {
                    while (left < right && nums[left] === nums[++left]) {}
                }
                if (sum >= target) {
                    while (left < right && nums[right] === nums[--right]) {}
                }
            }
            while (nums[j] === nums[j + 1]) j++
        }
        while (nums[i] === nums[i + 1]) i++
    }

    return res;
};